The BH equation is just one of a family of possible equations on the 2D lattice.

It's represented as

◾️◾️◾️
◾️◾️◾️
▫️◾️▫️

which tells us that the value of the center tile is determined by the values in the bottom left and bottom right.

Of course, we can consider other formations too. This notebook investigates this.

Equivilance¶

The BH representation is the same as:

▫️◾️◾️
◾️◾️◾️
▫️◾️◾️

since any equation satisfying the BH representation also would satisfy this. Simiarly,

◾️▫️◾️
▫️◾️◾️
◾️◾️◾️

is the same. Let's continue:

3x3 Matrix, with center always 0, can be "unwrapped" to the vector

[
(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(2,3)
(3,1)
(3,2)
(3,3)
]

We'd like a few matrices that perform reflections and rotations (about (2,2)). Consider the vertical reflection

(1,1) <-> (1,3) => 1 <-> 3
(2,1) <-> (2,3) => 4 <-> 6
(3,1) <-> (3,3) => 7 <-> 9

Or in matrix form, V

The horizontal reflection is

(1,1) <-> (3,1) => 1 <-> 7
(1,2) <-> (3,2) => 2 <-> 8
(1,3) <-> (3,3) => 3 <-> 9

with Matrix, H

Both are the same under transpose.

The single rotation is the most complex:

(1,1) -> (1,2) => 1 -> 2
(1,2) -> (1,3) => 2 -> 3
(1,3) -> (2,3) => 3 -> 6
(2,3) -> (3,3) => 6 -> 9
(3,3) -> (3,2) => 9 -> 8
(3,2) -> (3,1) => 8 -> 7
(3,1) -> (2,1) => 7 -> 4
(2,1) -> (1,1) => 4 -> 1

with matrix, R:

And $R^9 = R$, => $R^8 = I$

With these matrices, given a boolean array A, with A[5] == 0 (|{A}| = 256), we can ask, how many unique configurations up to modifications by R, H, and V. That is, A == B iff there exists a polynomial, p, in R, H, V, s.t. p(A) = B.

I'd like to find all unique A, up to this equivalence relation. Maybe first we count them.

Q: are R, H, and V abelian?

No, but almost. There are lots of simplifications:

$$ V^2 = I $$$$ H^2 = I $$$$ VH = HV $$$$ RHR = H $$$$ RVR = V $$$$ R^4 = VH = VH $$$$R^{-1} = R^7$$

Example: given the polynomial R^2 H R V R, this can be simplified:

$$ R^2 H R V R = R^2 H V = R^6 $$

I think the only polynomials are of the form:

$$ R^n$$$$ HR^nV $$$$ HR^n $$$$ R^nV $$$$ VR^nH $$$$ VR^n $$$$ R^nH $$

n <= 7

Why? we only need to consider $R^nVR^m$ and $R^nHR^m$ in the interior, since all other forms reduce to some power of R. But
$R^nVR^m = R^{n-1}RVRR^{m-1} = R^{n-1}VR^{m-1}$, and so on, so they eliminate themselves, until R or H is at the start or end.

Therefore there are at max 7 * 7 = 49 unique polynomials, but likely lots of redundancy in this. Code:

There are 30 classes. One of them is trivial (blank).

To keep things stable, our functional equation should normalize by the number of elements being added. Ex:

For eq.class 30,

$$ f(n,k) = 1/9 ( f(n-1, k-1) + f(n-1, k) + f(n-1, k+1) + ... + f(n+1, k+1) ) $$